Approximating the independence number via theϑ-function

We describe an approximation algorithm for the independence number of a graph. If a graph onn vertices has an independence numbern/k + m for some fixed integerk 3 and somem > 0, the algorithm finds, in random polynomial time, an independent set of size , improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size (m ^1/(k–1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the-function of ann vertex graph is at leastMn ^1–2/k for some absolute constantM, we describe another, related, efficient algorithm that finds an independent set of sizek. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the-function and the independence number of a graph onn vertices. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by a USA—Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences and by the Minkowski Minerva Center for Geometry at Tel Aviv University.This work was partly done while the author was at XEROX PARC and partly at DIMACS.     

Explicit construction of graph invariant for strongly pseudoconvex compact 3-dimensional rational CR manifolds

Let X be a strongly pseudoconvex compact 3-dimensional CR manifolds which bounds a complex variety with isolated singularities in some C^N. The weighted dual graph of the exceptional set of the minimal good resolution of V is a CR invariant of X; in case X has a tranversal holomorphic S¹ action, we show that it is a complete topological invariant of except for two special cases. When X is a rational CR manifolds, we give explicit algebraic algorithms to compute the graph invariant in terms of the ring structure of _k=0 m^k/m^k+1, where m is the maximal ideal of each singularity. An example is computed explicitly to demonstrate how the algorithms work.     

Distance-Regular Graphs with c i = b d-i and Antipodal Double Covers

Let be a distance-regular graph of diameter d and valency k > 2. Suppose there exists an integer s with d 2s such that c _i = b _d-i for all 1 i s. Then is an antipodal double cover.     

Association Schemes with Multiple Q-polynomial Structures

It is well known that an association scheme with has at most two P-polynomial structures. The parametrical condition for an association scheme to have two P-polynomial structures is also known. In this paper, we give a similar result for Q-polynomial association schemes. In fact, if , then we obtain exactly the same parametrical conditions for the dual intersection numbers or Krein parameters.     

Tractable Partially Ordered Sets Derived from Root Systems and Biased Graphs

We study new posets Q obtained by removing from a geometric lattice L ofa biased graph certain flats indexed by a simplicial complex . (One example of L is the lattice of flats of thevector matroid of a root system B _n .) We study the structureand compute the characteristic polynomial of Q. With certainchoices of L and , including ones for which Q is alattice interpolating between those of B _n and D _n , we observe curious relationships among the roots of thecharacteristic polynomials of Q, L, and .     

Weak Graph Map Homotopy and Its Applications∗

The authors introduce a notion of a weak graph map homotopy (they call it M-homotopy), discuss its properties and applications. They prove that the weak graph map homotopy equivalence between graphs coincides with the graph homotopy equivalence defined by Yau et al in 2001. The difference between them is that the weak graph map homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over the graph homotopy transformation. As its applications, they investigate the mapping class group of a graph and the 1-order MP-homotopy group of a pointed simple graph. Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is invariant up to the weak graph map homotopy equivalence.     

On bandwidth sums of graphs

ＯＮＢＡＮＤＷＩＤＴＨＳＵＭＳＯＦＧＲＡＰＨＳＹＡＯＢＩＮＧ（姚兵）;ＷＡＮＧＪＩＡＮＦＡＮＧ（王建方）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｉｈｗｅｓｔｅｔｅｒｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ,Ｌａｎｚｈｏｕ７３００７０,Ｃｈｉ...     

Two-Arc Transitive Graphs and Twisted Wreath Products

The paper addresses a part of the problem of classifying all 2-arc transitive graphs: namely, that of finding all groups acting 2-arc transitively on finite connected graphs such that there exists a minimal normal subgroup that is nonabelian and regular on vertices. A construction is given for such groups, together with the associated graphs, in terms of the following ingredients: a nonabelian simple group T, a permutation group P acting 2-transitively on a set , and a map F : Tsuch that x = x ^–1 for all x F() and such that Tis generated by F(). Conversely we show that all such groups and graphs arise in this way. Necessary and sufficient conditions are found for the construction to yield groups that are permutation equivalent in their action on the vertices of the associated graphs (which are consequently isomorphic). The different types of groups arising are discussed and various examples given.     

Simple expressions of the reflection and transmission coefficients of fundamental Lamb waves by a rectangular notch

The scattering of Lamb waves by a two-dimensional rectangular notch is investigated for rapid inspection of defects in a structure. To derive the reflection and transmission coefficients of the scattered waves in a simple way, the scattering caused by the notch is analyzed through the composition of individual scattering processes. Linear equations corresponding to the reflection and transmission coefficients are constructed along with scattering graphs. For an illustration of the efficacy of the presented method, the scattering of fundamental symmetric and anti-symmetric modes are inspected according to the depth and width of a notch in a plate. Validity of these expressions is demonstrated by the comparison of the theoretical analysis results with those from the finite element analysis.     

Some graft transformations and its application on a distance spectrum

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, we give some graft transformations that decrease and increase ?(G) and prove that the graph (obtained from the star S_n on n (n is not equal to 4, 5) vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while (obtained from a triangle K₃ by attaching pendent path P_n−3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices.